package leetcode.sorted;

import org.junit.Test;

import java.util.Arrays;

public class QuickSort  {





    @Test
    public void sort() throws Exception {
        // 对 arr 进行拷贝，不改变参数内容

        int[] arr = {-1,3,0,-2,7};
        QuickSort1(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));

    }

    public void QuickSort1(int[] arr, int left, int right) throws Exception {
        /**1.从数列中挑出一个元素，称为 “基准”（pivot）;

         2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
         在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

         3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；*/

        int pivot = arr[(left + right)/2];
        int temp = 0;
        //给下次递归限定范围
        int l = left;
        int r = right;

        while(left<right){
            while(arr[left] < pivot){
                left++ ;
            }
            while(arr[right] > pivot){
                right--;
            }

            if(left>=right){
                break;
            }
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;

            if(arr[left] == pivot){
                right--;
            }
            if(arr[right] == pivot){
                left++;
            }
        }
        if(left == right){
            left++;
            right--;
        }

        //左递归
        if(l<right){
            QuickSort1(arr,l,right);
        }

        //右递归
        if(left<r) {
            QuickSort1(arr, left, r);
        }
    }

//    //左递归
//        if(right>l) { //right = 4,l=0
//        QuickSort(arr, l, right);
//    }
//    //右递归
//        if(left <r) {//left = 0,r=0
//        QuickSort(arr, left, r);
//    }





    public void QuickSort(int[] arr, int left, int right) throws Exception {
        /**1.从数列中挑出一个元素，称为 “基准”（pivot）;

         2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
         在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

         3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；*/

        //给下次递归限定范围
        int l = left;
        int r = right;

        int mid = (left + right) /2;
        int pivot = arr[mid];
        int temp = 0;
        //进行分治，0 - mid 中大于mid->右边right
        //进行分治，mid - right 中小于mid->左面left
        while(left<right){

            while(arr[left] < pivot){
                left++;
            }
            while(arr[right] > pivot){
                right--;
            }

            if(left>=right){
                break;
            }
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
           /**
            * 如果给定一个数组{3，-1,0,2,3}，肯定右面已经拍好了，左边的跳出一个，这时候的双指针中的right
            * 会就会达到基数arr[mid]，{3，-1,0,2,3}
            * 则让arr[left] 和 基数发生交换。{0，-1,3,2,3}
            * 这时候的right指针是指向了3，left指向0；right--，于是-1和0互换，按以上顺序改变{-1,0，3,2,3}
            * 这时left=0；rgiht=1；
            * */
            // 这时left=0；right=1；进入下一个条件，left++；l=r=pivot，达到退出要求
            if(arr[right] == pivot){
                left++;
            }
            if(arr[left] == pivot){
                right--;
            }

        }
        //如何left和right在同一点结束，就需要加入这个条件
        if(left==right){
            left++;
            right--;
        }
        //左递归
        if(right>l) { //right = 4,l=0
            QuickSort(arr, l, right);
        }
        //右递归
        if(left <r) {//left = 0,r=0
            QuickSort(arr, left, r);
        }
    }

}

















